#define _CRT_SECURE_NO_WARNINGS 1
class MinStack
{
public:
    MinStack()
    {

    }

    void push(int val)
    {
        if (min_st.empty() || min_st.top() >= val)
        {
            min_st.push(val);
        }
        st.push(val);
    }

    void pop()
    {
        if (st.top() == min_st.top())
        {
            min_st.pop();
        }
        st.pop();
    }

    int top()
    {
        return st.top();
    }

    int getMin()
    {
        return min_st.top();
    }
    stack<int> st;
    stack<int> min_st;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */


class Solution {
public:
    bool IsPopOrder(vector<int> pushV, vector<int> popV) {
        int n = pushV.size();
        stack<int> s;
        int j = 0;

        for (int i = 0; i < n; i++)
        {
            while (j < n && (s.empty() || s.top() != popV[i]))
            {
                s.push(pushV[j]);
                j++;
            }
            if (s.top() == popV[i])
                s.pop();
            else
                return false;
        }
        return true;
    }
};




class Solution
{
    string nz[4] = { "+","-","*","/" };
public:
    int evalRPN(vector<string>& tokens)
    {
        stack<int> st;
        int ret = 0;
        int n = tokens.size();
        for (int i = 0; i < n; i++)
        {
            string& token = tokens[i];
            if (!(token == "+" || token == "-" || token == "*" || token == "/"))
                st.push(atoi(token.c_str()));

            for (int i = 0; i < 4; i++)
            {
                if (token == nz[i])
                {
                    int right = st.top();
                    st.pop();
                    int left = st.top();
                    st.pop();
                    switch (token[0]) {
                    case '+':
                        st.push(left + right);
                        break;
                    case '-':
                        st.push(left - right);
                        break;
                    case '*':
                        st.push(left * right);
                        break;
                    case '/':
                        st.push(left / right);
                        break;
                    }
                    break;
                }
            }
        }
        return st.top();
    }
};